package tencent;

/**
 * Author:   dengxin
 * Date:     2020/6/13 10:19 上午
 * 微信红包
 * 小明收到的红包中，某个红包金额的出现次数超过红包总数的一半，求该红包金额
 * 给定红包金额数组gifts[int]及其大小n，返回该红包金额，若没有红包金额超过总数的一半，返回0
 * 解法：
 * 1.Hash法(略)
 * 2.寻找水王法(最优)
 */
@SuppressWarnings("all")
public class qq2 {

    public int getValue(int[] gifts, int n) {
        //边界条件
        if (gifts.length!=n || n<=0) {
            return 0;
        }
        //计数器count，和当前记录值temp，出现次数技术times
        int count=0,temp=-1,times = 0;
        //遍历gifts
        for (int gift : gifts) {
            //如果count==0，设置当前gifts元素==temp，count==1
            if (count == 0) {
                temp = gift;
                count = 1;
                continue;
            }
            //如果count!=0，那么如果当前gifts元素==temp，则count++；如果当前gifts!=temp，则count--
            if (gift == temp) {
                count++;
            } else {
                count--;
            }
        }
        //如果count>0，则遍历数组，与当前temp值比较，获取temp出现的次数
        if (count > 0) {
            for (int value: gifts
                 ) {
                if (value == temp) {
                    times++;
                }
            }
        }
        //如果temp出现次数>数组元素个数的一半，则返回temp，否则返回0
        return times>(n/2)?temp:0;
    }
}
